package com.kevinkk.stackandqueue;

import java.util.*;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 */

public class TopKFrequentElements {
    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            // bucket数组用来记录，出现 i 次 的元素都有哪些，由于nums 数组的长度为 length，所以至多出现 length+1 种情况
            List<Integer>[] bucket = new ArrayList[nums.length+1];
            // 记录某个数字出现了多少次
            Map<Integer, Integer> map = new HashMap<>();
            for(int i : nums)
                map.put(i, map.getOrDefault(i, 0)+1);
            // bucket[i] 记录下出现 i 次的数字都有哪些
            for(int key : map.keySet()){
                if(bucket[map.get(key)] == null)
                    bucket[map.get(key)] = new ArrayList<>();
                bucket[map.get(key)].add(key);
            }
            int[] res = new int[k];
            int index = 0;
            // 出现次数最多的元素，因此倒叙遍历 bucekt
            for(int i = nums.length; i >= 0; i--){
                if(bucket[i] == null) continue;
                while(!bucket[i].isEmpty()){
                    res[index++] = bucket[i].get(0);
                    bucket[i].remove(0);
                    if(index == k) return res;
                }

            }
            return null;
        }
    }
}
